1. Field of the Invention
The present invention relates to the automatic synthesis of executable software code from a user specification. A particular application is the automatic code generation for valuing financial instruments.
2. Description of Problem Environment
Mathematicians, physicists, engineers, and analysts who build computer programs to solve partial differential equation (xe2x80x9cPDExe2x80x9d) modeling problems must be familiar not only with the mathematics and physics of their problems, but also with a variety of technological tools. Pragmatically, this problem solving process involves thinking in terms of the tools, e.g., numerical software libraries, existing codes, and systems for connection software components. Unfortunately, sometimes the emphasis must shift too early from the fundamentals of the problem to how to code a solution.
Current practice generally centers around mathematical libraries that provide code modules to be connected via subroutine calls. Such libraries are limited to the specific interface required to use each module of the library.
The predominance of tool considerations can obscure the model and cause modelers to think at too low a level of abstraction. This can lead to compromises that cause inaccurate or incomplete solutions. Some difficulties are:
Insufficient understanding of the underlying mathematics may lead to a choice of numerical methods that are inappropriate to the problem,
Higher-order methods tend to be avoided because they are too numerous to put into libraries and too tedious to code manually,
Lack of generality or incompleteness in available libraries can cause modelers to include similar shortcomings in their own models,
Unstated or poorly understood tool and component assumptions can lead to composition of software components in a way that violates their assumptions,
The assembly of a solution from pre-existing components often precludes significant optimizations that span multiple components, and
The assembly-of-components style of programming may also impose computing platform and language constraints not inherent in the modeling problem.
The shortcomings of conventional libraries have not escaped popular notice. To address some of the problems, both object-oriented libraries and expert systems have been proposed.
Object-oriented libraries can provide more generality by abstracting data structure representations, but they are usually not independent of the specific equations being solved or of properties such as spacial dimensionality and order of accuracy of the algorithm being used, which typically affects the data presentation. With any type of library, assembly and bottom-up optimization of individual modules is the user""s focus rather than top-down decision making and global optimization.
Expert systems can select and combine library modules relieving the user of some of the programming burden. However, expert systems alone do not address issues such as an appropriate specification level, generation of arbitrary higher-order methods, global and problem-specific optimization, and platform re-targeting.
One feature common to the best of libraries and expert systems is a good analysis of the application area. Expert systems generally start at an abstract level in terms of problem solving goals or tasks and their subproblems. Eventually these tasks must connect into the specific functionality provided by the library routines. Object-oriented libraries allow this contact to be made at a more abstract level. As part of the analysis process, classifications or taxonomies of problems and solution techniques are typically developed. The analysis information may be used in the design of objects, decision or planning rules, or library routine naming schemes.
Many problems in science, engineering, or finance can be modeled using partial differential equations. While finite difference techniques are widely used for finding a solution for these PDE problems, producing accurate software code to generate a solution is difficult and time consuming. Programming such software code requires extensive domain knowledge of the problem, an understanding of the math, an understanding of advanced computer science techniques, and extensive testing and debugging. Therefore, other techniques are often used to model such problems.
For example, privately traded derivative financial products comprised a $29 Trillion industry in 1996, growing at 37% annually. Investment banks and derivative brokers make extensive use of sophisticated mathematical models to price the instruments, and once sold, to hedge the risk in their positions. The models used are basically of four types: analytical models, and three versions of approximate numerical models: Monte Carlo, lattices (binomial and trinomial trees) and finite differences.
A host of simplifications, e.g., constant interest rates, constant volatility of the underlying assets, continuously paid dividends, etc., allow analytic solutions to the Black-Scholes equation, the basic partial differential equation describing derivative securities. These analytic solutions are packaged in software libraries of xe2x80x9canalyticsxe2x80x9d. Many packages exist. They may be used by traders for rough estimates, but all the assumptions required to make analytic solutions possible, usually render them too inaccurate for pricing complex derivative products. Major investment banks usually strip them out of any integrated software systems they may buy, and substitute their own numerical models.
Monte Carlo models calculate the value of an option by simulating thousands or millions of possible random paths the underlying assets prices may take, and averaging the option value over this set. Early exercise features, i.e., American options, cannot be priced, and the values of critical hedging parameters are often noisy. Option parameters calculated in this way may converge to the correct answer quite slowly.
In lattice methods the price paths are again simulated as a discrete series of branch points, at which an asset price may go up, down, or perhaps remain unchanged. These methods are popular and quite flexible, but they require many branch points in time for accuracy, (They converge to the correct answer like 1/N, where N is the number of time samples.) and they may be very difficult to construct, especially in multiple dimensions. If the branches cannot be made to xe2x80x9creconnectxe2x80x9d then the CPU time for these algorithms increases exponentially with N, rather than proportionately.
A solution based on finite difference solutions of the Black-Scholes partial differential equation and related equations is a desirable approach, but difficult to implement. Writing software solutions that solve such partial differential equations is time consuming and debugging difficult.
Another problem is that while it is widely assumed that current modeling techniques for financial processes are measured continuously, in the real financial world they are measured discretely. Often the difference is quite significant. The continuous measurement model may be too inaccurate to be useful. An example is the discrete sampling of an asset price, say at the end of a trading day, to determine if it has crossed a xe2x80x9cbarrierxe2x80x9d. Often option structure contain these barriers. An asset price crossing this barrier may xe2x80x9cknock-outxe2x80x9d an option, i.e., render it valueless. If a stock price crosses the barrier during the day but recrosses back before the end of trading, a continuous model of the option would be knocked out, but the discrete model would still be viable. There are similar differences between continuously and discretely sampled average and extremum prices which figure into Asian and lookback options.
There are, however, a number of problems where PDE solution methods are impractical. In such cases a methodology to generate a solution using Monte Carlo techniques is desirable. Examples of patents for valuing financial instruments include U.S. Pat. Nos. 5,940,810; 5,872,725; 5,819,237; 5,799,287; 5,790,442; 5,692,233 (incorporated by reference).
The problems outlined above are largely solved by the method and system of the present invention. That is, the present system provides the user with the ability to simply describe a problem, common in engineering, finance or science, and the system automatically transforms the problem into executable software code. The system and method hereof provide the ability to describe a problem and possible solution strategies at a high, abstract level, and the system uses its knowledge base to refine the problem in terms of finite difference solutions to partial differential equations (or other mathematical techniques, including Monte Carlo simulators). The system generates executable code that implements a solution.
Generally speaking, the method of the present invention automatically generates executable software code in a target language for a user defined problem. First, the method develops a problem specification for the user problem. Next, the method formulates a mathematical description of the problem specification, and finally, this method generates executable software code in the target language. The problem specification is developed using the user defined problem and comparing the user""s input with the system""s knowledge base. The system""s knowledge base includes refinement rules, optimizing transformations, heuristics, constraints, and defaults to not only assist in developing the problem specification, but to identify inconsistencies or invalid definitions.
The mathematical description of the problem specification generates a coordinate free set of equations describing the problem specification. Additionally, the mathematical description produces a template particularly useful for solving the set of equations. Preferably, the templates include procedural control structures as well as data declarations. From the templates and equations, the method develops a data structure and generates pseudo-code describing the user problem. The pseudo-code is translated into source code in the target language, e.g. Fortran or C.
The knowledge base includes a number of templates arranged as hierarchy of classes. Such template classes might include solvers, time evolution algorithms, as well as stepping algorithms. Many methods are available for solving these equations, and in particular, a Monte Carlo simulation proves useful. Preferably, the method uses symbolic algebra with general coordinates and dimensional parameters to formulate the mathematical description of the problem specification.
The system of the present invention automatically generates executable software code based on the user defined specification. Broadly speaking, the system includes a knowledge base which contains constraints, heuristics, and defaults for developing a problem specification based on the user defined specification. The system additionally includes a computer algebra module for writing equations indicative of the problem specification. A class of templates are included in the system for specifying the boundary conditions and for describing the evolution of the equations. Preferably, the templates also generate the pseudo-code reflecting the specified algebra algorithms and equations. The system then generates source code in the specified target language and architecture.
The method of the present invention is particularly useful for valuing a financial option. Generally, the method for valuing a financial option begins with modeling the option with a partial differential equation and constructing a finite difference solution for the partial differential equation or a set of partial differential equations modeling Monte Carlo methods. In on embodiment Stochastic differential equations are xe2x80x9cSDExe2x80x9d are specified to reflect the Monte Carlo simulation or converted to partial differential equations. The stochastic differential equations are discretized and pseudo-code is generated for the finite difference solution; pseudo-code is then transformed into the target language and compiled into executable code. A valuation of the financial option is computed using specified factors or parameters. This method of valuing a financial option is particularly useful for analyzing the effect of discrete events on valuation of the option. Such a discrete advent may comprise a valuation of the option if the asset price crosses a certain barrier price, or the number of days an asset price was below or above a certain barrier value.